package primary.code02_Sort;

/**
 * 求小和（复杂度 N*LogN）
 * 对于数组中的每个数，左侧比该数小的数求和；
 * 归并时计算小和，并且可以通过坐标计算小和数量（有效利用比较）
 */
public class Code02_MinSum {

    private static int getMinsum(int[] arr, int l, int r) {
        if (l >= r) {
            return 0;
        }
        int m = (l + r) / 2;
        return getMinsum(arr, l, m) + getMinsum(arr, m + 1, r) + mergeMinsumTest(arr, l, m, r);
    }

    private static int mergeMinsum(int[] arr, int l, int m, int r) {
        int[] helper = new int[r - l + 1];
        int p1 = l;
        int p2 = m + 1;
        int littleSum = 0;
        for (int i = 0; i < helper.length; i++) {
            if (p1 > m) helper[i] = arr[p2++];
            else if (p2 > r) {
//                littleSum += arr[p1] * (r - p2 + 1);//不产生小和，(r - p2 + 1) = 0
                helper[i] = arr[p1++];
            } else {
                if (arr[p1] < arr[p2]) {
                    littleSum += arr[p1] * (r - p2 + 1);//产生小和
                    helper[i] = arr[p1++];
                } else {
                    helper[i] = arr[p2++];
                }
            }
        }
        for (int j = 0; j < helper.length; j++) {
            arr[l + j] = helper[j];
        }
        return littleSum;
    }

    private static int mergeMinsumTest(int[] arr, int l, int m, int r) {
        int res = 0;
        int p1 = l;
        int p2 = m + 1;
        int[] helper = new int[r - l + 1];
        int index = 0;
        while (p1 <= m && p2 <= r) {
            if (arr[p1] < arr[p2]) {
                res += arr[p1] * (r - p2 + 1);
                helper[index++] = arr[p1++];
            } else {
                helper[index++] = arr[p2++];
            }
        }
        for (int i = p1; i <= m; i++) {
            helper[index++] = arr[p1++];
        }
        for (int i = p2; i <= r; i++) {
            helper[index++] = arr[p2++];
        }
        for (int i = 0; i < helper.length; i++) {
            arr[l + i] = helper[i];
        }
        return res;
    }

    /**
     * 16
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 2, 5, 1, 1};
        System.out.println(getMinsum(arr, 0, arr.length - 1));//16
    }
}
